//给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 
//
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。 
//
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 
//
// 假设你总是可以到达数组的最后一个位置。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 
//
// 示例 2: 
//
// 
//输入: nums = [2,3,0,1,4]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 10⁴ 
// 0 <= nums[i] <= 1000 
// 
// Related Topics 贪心 数组 动态规划 👍 1711 👎 0


package com.cjl.leetcode.editor.cn;
/**
 * [P45]_跳跃游戏 II
 * @author cjl
 * @date 2022-07-23 14:57:12
 */
public class P45_JumpGameIi{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P45_JumpGameIi().new Solution();
//          System.out.println("args = " + solution.jump(new int[]{0})); //0
          System.out.println("args = " + solution.jump(new int[]{1,2,3})); //2
//        System.out.println("args = " + solution.jump(new int[]{3,4,3,1,0,7,0,3,0,2,0,3}));//3
//          System.out.println("args = " + solution.jump(new int[]{7,0,9,6,9,6,1,7,9,0,1,2,9,0,3})); //2
    }
    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：遍历，取每一步可跳到最大值，如果当前位置可跳到最大值比历史最大值大，则说明需要额外跳一步，否则不+1；
         * @param nums
         * @return
         */
//    public int jump(int[] nums) {
//        if(nums.length == 1){
//            return 0;
//        }
//        int curmax = 0, nextmax = 0;
//        int step = 0;
//        for(int i = 0 ; i < nums.length; i++){
//            if(i == curmax){
//                //注意：此处curmax 应为两个值大最大值，表示在i位置，跳跃可达到大最大位置
//                curmax = Math.max(nums[i] + i, nextmax);
//                step++;
//            }
//            if(nums[i] + i > nextmax){
//                nextmax = nums[i] + i;
//            }
//            if(curmax >= nums.length -1){
//                return step;
//            }
//            if(nextmax >= nums.length -1){ //终点
//                return step +1;
//            }
//        }
//        return step;
//    }

        /**
         *
         * 每一步可以达到的最大距离
         * 到达最大位置时，下一次可到达的最大位置
         * @param nums
         * @return
         */
        public int jump(int[] nums) {
            int step = 0;
            int curMaxSize = 0;
            int nextMasSize = 0;
            for(int i =0; i < nums.length; i++){
                if(curMaxSize >= nums.length-1){
                    return step;
                }
                //到达最大位置前，可以计算下次可达到的最大位置；
                nextMasSize = Math.max(nums[i]+i, nextMasSize);
                if(i == curMaxSize){
                    step++;
                    curMaxSize = nextMasSize;
                }
            }
            return step;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}